class Solution {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    public int dfs(TreeNode root){
        if(root==null)
            return 0;
        // 只有左右子树贡献>0时才算数
        int ret1 = Math.max(dfs(root.left),0);
        int ret2 = Math.max(dfs(root.right),0);

        // 更新答案
        ans = Math.max(ans,ret1+ret2+root.val);

        // 返回节点的最大贡献值
        return Math.max(ret1,ret2)+root.val;
    }
}